package com.algorithm.cjm.july.linkedlist;

/**
 * 链表翻转。给出一个链表和一个数k，比如，链表为1→2→3→4→5→6，k=2，则翻转后2→1→6→5→4→3，
 * 若k=3，翻转后3→2→1→6→5→4，若k=4，翻转后4→3→2→1→6→5，用程序实现。
 *
 * @Author: Jie Ming Chen
 * @Date: 2019-04-24
 * @Version 1.0
 */
public class RotateLinkedList {
    public static void main(String[] args) {
        RotateLinkedList linkedList = new RotateLinkedList();
        Node node = new Node(10);
        Node node1 = new Node(9);
        Node node2 = new Node(8);
        Node node3 = new Node(7);
        node.next = node1;
        node1.next = node2;
        node2.next = node3;
        linkedList.rotate(node, 1);
    }

    // TODO 链表
    private Node rotate(Node node, int k) {
        Node left = null;
        Node right = node;
        // k = 1
        while (k-- > 0) {
            right = right.next;
        }

        Node res = rotateNode(left);
        res.next = rotateNode(right);

        return res;
    }

    // 旋转链表
    private Node rotateNode(Node node) {
        Node pre = null;
        Node next = node;

        while (next != null) {
            // 下一个节点临时存储
            Node temp = next.next;

            // 反转链表的核心，取当前的node节点的数据，把它下一个指针指向前一个节点，然后把node复制给当前节点
            next.next = pre;
            pre = next;

            next = temp;
        }
        return pre;
    }
}
